package Algorithms;

/**
 * 遗传算法类
 * @author 车宗绍Che Zongshao
 * @date 2015/1/7
 */

import java.util.LinkedList;
import java.util.Random;

import utils.Graph;
import utils.Node;

public class GA {

	private int popSize = 10;
	private int D = 5;
	private Node[][] pop;
	private Node[][] newPop;
	private int maxGens = 10;
	private double pCrossover = 0.2;
	private double pMutation = 0.3;
	private double alpha = 0.5;
	
	/**
	 * 执行GA算法
	 */
	public Node[] doGA() {
		// TODO 生成初始种群
		pop = new Node[popSize][D];
		for (int i = 0; i < popSize; i++) {
			int[] index = this.randomPath(2, 4);
			pop[i][0] = Graph.generateNode(1);
			pop[i][D-1] = Graph.generateNode(Graph.getTarget().getName());
			for (int j = 0; j < index.length; j++) {
				pop[i][j+1] = Graph.generateNode(index[j]);
			}
			pop[i][D-1].setFn(this.calcFit(pop[i]));
		}
		// TODO 初始种群排序
		this.bubbleSort(pop);
		
		for (int gen = 0; gen < maxGens; gen++) {
			// TODO 生成新种群
			newPop = new Node[popSize][D];
			int count = 0;		// 新种群个体数计数器
			while (count < popSize) {
				// 选择亲本
				this.eval(pop);
				if (count == 0) {
					newPop[count] = pop[0];
					newPop[count + 1] = pop[1];
					count += 2;
					continue;
				} else {
					newPop[count] = this.select();
					newPop[count + 1] = this.select();
				}
				
				// 交叉
				this.crossover(newPop[count], newPop[count + 1]);
				
				count += 2;
			}
			
			// 变异
			this.mutation();
			
			// 排序
			this.bubbleSort(newPop);
			
			pop = newPop;
			System.out.print(pop[0][D-1].getFn() + ",");
		}
		System.out.println();
		return pop[0];
	}
	
	/**
	 * 随机生成遍历路径索引，范围1~size
	 * @param inf	下界
	 * @param sup	上界
	 * @return
	 */
	public int[] randomPath(int inf, int sup) {
		if (inf > sup) {
			int temp = inf;
			inf = sup;
			sup = temp;
		}
		LinkedList<Integer> temp = new LinkedList<Integer>(); // 中介
		Random rand = new Random();
		int[] result = new int[sup - inf + 1];		// 结果
		// 初始化temp
		for (int i = inf; i <= sup; i++) {
			Integer integer = new Integer(i);
			temp.add(integer);
		}
		// 随机取数
		for (int i = 0; i < result.length; i++) {
			int r = rand.nextInt(result.length - i);
			result[i] = temp.get(r);
			temp.remove(r);
		}
		return result;
	}
	
	/**
	 * 变异
	 * 对整个newPop进行变异
	 */
	private void mutation() {
		Random random = new Random();
		for (int i = 1; i < newPop.length; i++) {
			if (pMutation > random.nextDouble()) {
				// 交换r1和r2位置的节点
				int r1 = random.nextInt(D-2) + 1;
				int r2 = random.nextInt(D-2) + 1;
				Node temp = null;
				temp = newPop[i][r1];
				newPop[i][r1] = newPop[i][r2];
				newPop[i][r2] = temp;
				// 重新计算fit
				newPop[i][D-1].setFn(this.calcFit(newPop[i]));
			}
		}
	}
	
	/**
	 * 交叉
	 * 直接改变p1和p2
	 * @param p1
	 * @param p2
	 */
	public void crossover(Node[] p1, Node[] p2) {
		Random random = new Random();
		if (pCrossover > random.nextDouble()) {
			// 交换r1和r2位置之间的节点
			int r1 = random.nextInt(D);
			int r2 = random.nextInt(D);
			if (r1 > r2) {
				int temp = r1;
				r1 = r2;
				r2 = temp;
			}
			// 交换
			for (int i = r1; i <= r2; i++) {
				Node temp = null;
				temp = p1[i];
				p1[i] = p2[i];
				p2[i] = temp;
			}
			
			// 消除冲突
			for (int i = 0; i < D; i++) {
				if (i == r1) {
					i = r2;
					continue;
				}
				for (int j = r1; j <= r2; j++) {
					if (p1[i].getName() == p1[j].getName()) {
						p1[i] = p2[j];
						j = r1-1;
						continue;
					}
					if (p2[i].getName() == p2[j].getName()) {
						p2[i] = p1[j];
						j = r1-1;
						continue;
					}
				}
			}
			// 重新计算适应度fit
			p1[D-1].setFn(this.calcFit(p1));
			p2[D-1].setFn(this.calcFit(p2));
		}
	}
	
	/**
	 * 选择一个亲本 依据轮盘赌概率
	 * @return
	 */
	private Node[] select() {
		Random random = new Random();
		Node[] result = new Node[D];
		double r = random.nextDouble() * pop[pop.length-1][D-1].getGn();
		for (int i = 0; i < pop.length; i++) {
			if (pop[i][D-1].getGn() >= r) {
				for (int j = 0; j < D; j++) {
					result[j] = Graph.generateNode(pop[i][j].getName());
				}
				return result;
			}
		}
		return null;
	}
	
	/**
	 * 轮盘赌 用于select
	 */
	private void eval(Node[][] pop) {
		pop[0][D-1].setGn(alpha);
		for (int i = 1; i < pop.length; i++) {
			pop[i][D-1].setGn(pop[i-1][D-1].getGn() + alpha*Math.pow(1-alpha, i));
		}
	}
	
	/**
	 * 冒泡排序，fit大的个体排在前面
	 */
	private void bubbleSort(Node[][] pop) {
		Node[] tempPath = new Node[D];
		for (int i = 0; i < pop.length; i++) {
			for (int j = pop.length - 1; j > i; j--) {
				if (pop[j][D-1].getFn() > pop[j-1][D-1].getFn()) {
					tempPath = pop[j];
					pop[j] = pop[j-1];
					pop[j-1] = tempPath;
				}
			}
		}
	}
	
	/**
	 * 计算路径适应度=1/总长度
	 * @param path
	 * @return 适应度
	 */
	private double calcFit(Node[] path) {
		double pathLength = 0.0;
		for (int i = 0; i < path.length - 1; i++) {
			try {
				pathLength += path[i].getEdge(path[i+1].getName()).getLength();
			} catch (java.lang.NullPointerException e) {
				System.out.print("error path:");
				for(int j = 0; j < path.length; j++) {
					System.out.print(path[j].getName());
				}
				System.out.println();
			}
			
		}
		return 1/pathLength;
	}
}